package practice1_100;

import java.util.*;

public class Practice103 {
    //这题用双栈结构来解题
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if(root==null) return new LinkedList<>();

        List<List<Integer>> list=new LinkedList<>();
        Stack<TreeNode> stack=new Stack<>();
        Stack<TreeNode> stack1=new Stack<>();

        stack.push(root);
        int level=0;
        Order(stack,stack1,level,list);
        return list;
    }


    public void Order(Stack<TreeNode> stack,Stack<TreeNode> stack1, int level, List<List<Integer>> list) {
        while (!stack.isEmpty()||!stack1.isEmpty()){
            if(level%2==0){//1，3，5，queue出，stack进栈
                List<Integer> temp=new ArrayList<>();
                while (!stack.isEmpty()){
                    TreeNode treeNode=stack.pop();
                    temp.add(treeNode.val);
                    if(treeNode.left!=null) stack1.push(treeNode.left);
                    if(treeNode.right!=null) stack1.push(treeNode.right);
                }
                list.add(temp);
                level++;
            }else {//2,4,6,8 Stack
                List<Integer> temp=new ArrayList<>();
                while (!stack1.isEmpty()){
                   TreeNode treeNode= stack1.pop();
                   temp.add(treeNode.val);
                    if(treeNode.right!=null) stack.add(treeNode.right);
                    if(treeNode.left!=null) stack.add(treeNode.left);
                }
                list.add(temp);
                level++;
            }
        }
    }

    public static void main(String[] args) {
        //[3,9,20,null,null,15,7]
       List list= new Practice103().zigzagLevelOrder(new TreeNode(3,new TreeNode(9,new TreeNode(13),new TreeNode(99)),new TreeNode(20,new TreeNode(15),new TreeNode(7))));
        System.out.println(list);
        System.out.println(-12>>7);
    }
}
